import java.util.*;

/**
 * @author shuang
 * @date 2022/5/1 23:05
 * 773. 滑动谜题
 * https://leetcode-cn.com/problems/sliding-puzzle/
 */
public class Solutions_773 {
    public static void main(String[] args) {
        // 解释：交换 0 和 5 ，1 步完成
        int[][] board1 = {{1, 2, 3}, {4, 0, 5}};  // output: 1

        // 无法完成
        int[][] board2 = {{1, 2, 3}, {5, 4, 0}};  // output: -1

        /*
         * 需移动 5 次
         * 尚未移动: {{4, 1, 2}, {5, 0, 3}}
         * 移动 1 次: {{4, 1, 2}, {0, 5, 3}}
         * 移动 2 次: {{0, 1, 2}, {4, 5, 3}}
         * 移动 3 次: {{1, 0, 2}, {4, 5, 3}}
         * 移动 4 次: {{1, 2, 0}, {4, 5, 3}}
         * 移动 5 次: {{1, 2, 3}, {4, 5, 0}}
         */
        int[][] board3 = {{4, 1, 2}, {5, 0, 3}};  // output: 5

        List<int[][]> inputs = new ArrayList<>();
        inputs.add(board1);
        inputs.add(board2);
        inputs.add(board3);

        Solutions_773 obj = new Solutions_773();
        for (int[][] input : inputs) {
            int result = obj.slidingPuzzle(input);
            System.out.println(result);
        }
    }

    /**
     * neighbors[0] = {1, 3}：表示元素 0 若处于索引 0 上，则可以与索引 1，索引 3 位置上的元素进行交换（因为相邻）
     * neighbors[1] = {0, 2, 4}：表示元素 0 若处于索引 1 上，则可以与索引 0，索引 2, 索引 4 位置上的元素进行交换（因为相邻）
     */
    private int[][] neighbors = {{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
    private Queue<String> queue;
    private Set<String> set;

    /**
     * 解题思路：BFS + neighbors 的定义与交换的过程
     * @param board
     * @return
     */
    private int slidingPuzzle(int[][] board) {
        StringBuilder sb = new StringBuilder(6);
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                sb.append(board[i][j]);
            }
        }
        String initStr = sb.toString();
        if (isRight(initStr)) {
            return 0;
        }

        int step = 0;
        queue = new LinkedList<>();
        queue.add(initStr);
        set = new HashSet<>();
        set.add(initStr);

        while (!queue.isEmpty()) {
            // 交换次数加 1
            step ++;
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String str = queue.poll();
                List<String> nextStrs = getSwapStrList(str);
                for (String nextStr : nextStrs) {
                    if (isRight(nextStr)) {
                        return step;
                    }
                    if (set.contains(nextStr)) {
                        continue;
                    }
                    // 未遍历过的情况
                    queue.add(nextStr);
                    set.add(nextStr);
                }
            }
        }
        // 无法完成最终的谜板
        return -1;
    }

    /**
     * 根据 0 元素所在的位置，与相邻元素交换后，记录下所有可能组成的字符串
     * @param str
     * @return
     */
    private List<String> getSwapStrList(String str) {
        List<String> list = new ArrayList<>();
        int index = str.indexOf('0');
        char[] charArray = str.toCharArray();
        // 0 与相邻索引上的元素进行交换
        int[] canSwap = neighbors[index];
        for (int j : canSwap) {
            // 交换
            swap(charArray, index, j);
            // 交换后的结果，记录到 list 中
            list.add(String.valueOf(charArray));
            // 还原
            swap(charArray, index, j);
        }
        return list;
    }

    /**
     * 交换数组中，两个索引上的元素
     * @param array
     * @param x
     * @param y
     */
    private void swap(char[] array, int x, int y) {
        char temp = array[x];
        array[x] = array[y];
        array[y] = temp;
    }

    /**
     * 检验字符串是否已经完成谜板
     * @param str
     * @return
     */
    private boolean isRight(String str) {
        return "123450".equals(str);
    }
}

